import math
class Solution(object):
    def numOfWays(self, nums):
        base = 10 ** 9 + 7

        def dfs(nums):
            n = len(nums)
            if n <= 1:
                return 1
            left_num = []
            right_num = []
            for i in range(1, n):
                if nums[i] > nums[0]:
                    right_num.append(nums[i])
                if nums[i] < nums[0]:
                    left_num.append(nums[i])
            m1 = len(left_num)
            m2 = len(right_num)
            return (math.comb(m1 + m2, m1) * dfs(left_num) * dfs(right_num)) % base

        return dfs(nums) - 1

data = Solution()
nums = [3, 4, 5, 1, 2]
print(data.numOfWays(nums))
